package com.lsa.cormen.ch24.samples;

import java.io.IOException;
import java.util.LinkedList;
import java.util.List;

import com.lsa.helpers.IConverter;
import com.lsa.helpers.graph.AdjGraph;
import com.lsa.helpers.graph.TgfGraphFactory;

public class TopsortSample {
    
    private static int time = 0;
    
    public static void main(String[] args) throws IOException {
        AdjGraph<VData, Object> g = new AdjGraph<VData, Object>(true, 11);
        for (int u = 0; u < g.nodeCount(); u++) {
            final VData vdata = new VData(Color.WHITE);
            vdata.vertex = u;
            g.setNodeAttr(u, vdata);
        }
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(4, 5);
        
        g.addEdge(1, 6);
        g.addEdge(6, 7);
        g.addEdge(7, 5);
        g.addEdge(7, 9);
        g.addEdge(6, 8);
        g.addEdge(8, 9);
        g.addEdge(8, 10);
        
        LinkedList<Integer> topSorted = new LinkedList<Integer>();
        dfs(g, 0, topSorted);
        
        for (int i = 1; i <= topSorted.size(); i++) {
            System.out.print(String.format("%2s ", i) );
        }
        System.out.println();
        
        for (Integer u : topSorted) {
            System.out.print(String.format("%2s ", u) );
        }
        
        TgfGraphFactory.saveGraphAsTgf(g, 
                new IConverter<VData,String>() {
                    @Override
                    public String convert(VData data) {
                        return "" + data.vertex + " f=" + data.f;
                    }
                }, 
                new IConverter<Object,String>() {
                    @Override
                    public String convert(Object data) {
                        return ""+data;
                    }
                }, "data/gen/small_tmp2.tgf");
    }
    
    public static void dfs(AdjGraph<VData, Object> g, int u, LinkedList<Integer> topSorted) {
        List<Integer> adj = g.adjacencyList(u);
        
        g.nodeAttr(u).c = Color.GRAY; 
        g.nodeAttr(u).d = ++time;
        
        for (Integer v : adj) {
            if (Color.WHITE == g.nodeAttr(v).c) {
                dfs(g, v, topSorted);
            }
        }
        
        g.nodeAttr(u).c = Color.BLACK;
        g.nodeAttr(u).f = ++time;
        
        topSorted.addFirst(u);
    }
    
    public static enum Color{
        WHITE,
        GRAY,
        BLACK
    }
    
    private static class VData {
        Color c;
        int vertex;
        
        int d; // discovery time
        int f; // finish time
        
        private VData(Color color) {
            this.c = color;
        }
    }
}
